package java_0220.leetcode;

/**
 * 二叉搜索树（BST）变为有序双向链表
 */
public class NumJZ36_ConvertTree2 {
    TreeNode head;
    TreeNode prev;//前驱节点
    public TreeNode Convert(TreeNode pRootOfTree) {
    if(pRootOfTree==null){
        return null;
    }
    //处理左子树转为双向链表
        Convert(pRootOfTree.left);
    //处理根节点的连接
        //prev为空，说明prev的下一位是待处理的根节点并且还是头节点
        //prev不为空，说明下一位节点不是头节点
        if(prev!=null){
            prev.right=pRootOfTree;
            pRootOfTree.left=prev;
            prev=prev.right;
        }else{
            head=pRootOfTree;
            prev=head;
        }

        //处理右子树转为双向链表
        Convert(pRootOfTree.right);
        return head;
    }
}
